package com.arron.algorithm.leetcodetop100.前缀和;

import java.util.HashMap;
import java.util.Map;

/**
 * 560. 和为 K 的子数组
 */
public class 和为K的子数组 {

    /**
     * 使用前缀和
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {


        int[] prefixSum = new int[nums.length+1];

        prefixSum[0] = 0;
        int count = 0;
        for (int i = 1; i < prefixSum.length; i++) {
                prefixSum[i] = prefixSum[i-1] + nums[i-1];
        }

        for (int i = 0; i < prefixSum.length; i++) {
            for (int j = i+1; j < prefixSum.length; j++) {

                if (prefixSum[j] - prefixSum[i] == k){
                    count++;
                }

            }

        }
        return count;

    }


    /**
     * 使用前缀和 + hash
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum_plus(int[] nums, int k) {
        Map<Integer/*前缀和*/,Integer/*出现的次数*/> prefixCountMap = new HashMap<>();

        //处理一些特殊值，比如 数组 nums = [1]，k =1;
        prefixCountMap.put(0,1);

        int sum = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = sum+nums[i];

            if (prefixCountMap.containsKey(sum-k)){
                count += prefixCountMap.get(sum-k);
            }
            prefixCountMap.put(sum,prefixCountMap.getOrDefault(sum,0)+1);
        }

        return count;
    }
}
